package 树;

import 抽象数据类型.TreeNode;
import 树.遍历.LevelTraverse;

import static 树.构造树.BuildTreeVoid;

/**
 * @description: 最近父节点
 * @author: ywk
 * @date: 2020-06-21
 */
public class LCA extends LevelTraverse {
    public static void main(String[] args) {
        String[] pre = ("A,B,D,E,C,F,G").split(",");
        String[] mid = ("D,B,E,A,F,C,G").split(",");
        TreeNode root = BuildTreeVoid(pre, mid, 0, pre.length - 1);
        System.out.println(LCA(root, root.right.left, root.right.right).getVal());
    }

    //最近父节点
    public static TreeNode LCA(TreeNode root, TreeNode a, TreeNode b) {
        TreeNode left,right;
        if (root == null) {
            return root;
        }
        if (root == a || root == b) {
            return  root;
        }
        left = LCA(root.getLeft(), a, b);
        right = LCA(root.getRight(), a, b);
        if (left != null && right != null) {
            return root;
        }else{
            return left == null ? right : left;
        }
    }

}
